package leetcode.editor.week.week313;

import java.util.Arrays;

// 6195. 对字母串可执行的最大删除数
// https://leetcode.cn/problems/maximum-deletions-on-a-string/
public class Solution6195 {
    // https://leetcode.cn/problems/maximum-deletions-on-a-string/solution/xian-xing-dppythonjavacgo-by-endlesschen-gpx9/
    // https://leetcode.cn/problems/maximum-deletions-on-a-string/solution/by-yingying_-4yr3/
    public int deleteString(String s) {
        int n = s.length();

        // lcp[i][j] 表示[i:]和[j:]的最长公共前缀
        int[][] lcp = new int[n][n];
        for (int i = n - 2; i >= 0; i--) {
            for (int j = n - 1; j > i; j--) {
                if (j == n - 1) lcp[i][j] = s.charAt(i) == s.charAt(j) ? 1 : 0;
                else lcp[i][j] = s.charAt(i) == s.charAt(j) ? lcp[i + 1][j + 1] + 1 : 0;
            }
        }

        // dp[i]表示对[i:]删除的最大次数
        int[] dp = new int[n];
        Arrays.fill(dp, 1);    // 每个字符删除最大操作都是1
        for (int i = n - 1; i >= 0; i--) {
            for (int j = 1; j + i < n; j++) {
                // 如果s[i : i + j] = s[i + j : i + 2j]，此时就有相同的前缀
                // 满足是lcp[i][i + j] >= j，说明s[i:]和s[i+j:]的最长公共前缀长度大于s[i:j]这个子串的长度
                // 那么此时删除操作就可以为 dp[i] = dp[i + j] + 1
                // 例如: aabab，此时lcp[1][3] = 2，所以dp[1] = dp[3] + 1
                if (lcp[i][i + j] >= j) dp[i] = Math.max(dp[i], 1 + dp[i + j]);
            }
        }

        // 由于倒着推过来，所以返回dp[0]
        return dp[0];
    }
}
